package com.lun.medium;

import java.util.HashMap;
import java.util.Map;

import com.lun.util.BinaryTree.TreeNode;

public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
	
	//方法一：我写的，提交给系统，报超时
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    	return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, // 
    		 int[] inorder, int inStart, int inEnd) {
    
    	if(preStart > preEnd) return null;
    	
    	TreeNode parent = new TreeNode(preorder[preStart]);
    	
    	//find parent's value in inorder sequence
    	int parentIndexInInorder = findIndex(inorder, parent.val, inStart, inEnd);

    	//在preorder找出最右边界，为下回递归作准备
    	int nextPreEnd = preStart;
    	for(int i = inStart; i <= parentIndexInInorder - 1; i++) {
    		int index = findIndex(preorder, inorder[i], preStart + 1, preEnd);
    		nextPreEnd = Math.max(nextPreEnd, index);
    	}
    	
    	parent.left = buildTree(preorder, preStart + 1, nextPreEnd, // 
    			inorder, inStart, parentIndexInInorder - 1);
    	parent.right = buildTree(preorder, nextPreEnd + 1, preEnd, 
    			inorder, parentIndexInInorder + 1, inEnd);
    	
    	return parent;
    }    
    
    private int findIndex(int[] array, int targetValue, int start, int end) {    	
    	if(start > end)
    		return -1;
    	for(int i = start; i <= end; i++) {
    		if(array[i] == targetValue)
    			return i;
    	}
    	return -1;
    }
    
    
    //方法二：方法一的改进版，使用map代替暴力查找，提交给系统，虽接受，但很耗时
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
    	Map<Integer, Integer> preMap = makeValue2IndexMap(preorder);
    	Map<Integer, Integer> inMap = makeValue2IndexMap(inorder);
    	return buildTree2(preorder, preMap, 0, preorder.length - 1,// 
    			inorder, inMap, 0, inorder.length - 1);
    }
    
    private TreeNode buildTree2(int[] preorder, Map<Integer, Integer> preMap, int preStart, int preEnd, // 
   		 int[] inorder, Map<Integer, Integer> inMap,  int inStart, int inEnd) {
   
	   	if(preStart > preEnd) return null;
	   	
	   	TreeNode parent = new TreeNode(preorder[preStart]);
	   	
	   	//find parent's value in inorder sequence
	   	int parentIndexInInorder = inMap.getOrDefault(parent.val, -1);
	
	   	//在preorder找出最右边界，为下回递归作准备
	   	int nextPreEnd = preStart;
	   	for(int i = inStart; i <= parentIndexInInorder - 1; i++) {
	   		int index = preMap.getOrDefault(inorder[i], -1);
	   		nextPreEnd = Math.max(nextPreEnd, index);
	   	}
	   	
	   	parent.left = buildTree2(preorder, preMap, preStart + 1, nextPreEnd, // 
	   			inorder, inMap, inStart, parentIndexInInorder - 1);
	   	parent.right = buildTree2(preorder, preMap, nextPreEnd + 1, preEnd, 
	   			inorder, inMap, parentIndexInInorder + 1, inEnd);
	   	
	   	return parent;
    }
    
    private Map<Integer, Integer> makeValue2IndexMap(int[] array){
    	Map<Integer, Integer> map = new HashMap<>();
    	for(int i = 0; i < array.length; i++)
    		map.put(array[i], i);
    	return map;
    }
    
    
    //方法三：别人写，性能颇佳
    public TreeNode buildTree3(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inMap = new HashMap<>();

        for(int i = 0; i < inorder.length; i++)
            inMap.put(inorder[i], i);

        TreeNode root = buildTree3(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
        return root;
    }

    public TreeNode buildTree3(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
        if(preStart > preEnd || inStart > inEnd) return null;

        TreeNode root = new TreeNode(preorder[preStart]);
        int inRoot = inMap.get(root.val);
        int numsLeft = inRoot - inStart;

        root.left = buildTree3(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);
        root.right = buildTree3(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap);

        return root;
    }
    
}
